1400C - Binary String Reconstruction - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define ll long long int

// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

#define ull unsigned long long 
#define lld long double
#define lcm(x,y) (x/__gcd(x,y)*y)
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define ppb pop_back
#define ff first
#define ss second
#define PI 3.141592653589793238462
#define setbit __builtin_popcountll
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define fr(i ,t , n) for (int i = t; i <= n; i++)
#define ceilval(a,b) ((a / b) + ((a % b) != 0));
#define endl "\n"
#define ub upper_bound
#define lb lower_bound
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif

void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}

const ll M=1e9+7;
ll binexp(ll a,ll b,ll m){
    ll ans=1;
    while(b){
        if(b&1){
            ans=(1LL*ans*a)%m;
        }
        a=(1LL*a*a)%m;
        b=(b>>1);
    }
    return ans;
}

bool ispal(string S){
    for (int i = 0; i < S.length() / 2; i++) {
        if (S[i] != S[S.length() - i - 1]) return 0;
    }
    return 1;
}

bool isPrime(ll n){
    if (n <= 1) return 0;
    if (n == 2 || n == 3) return 1;
    if (n % 2 == 0 || n % 3 == 0) return 0;
    for (ll i = 5; i <= sqrt(n); i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return 0;
     return 1;
}

vector<int> pfsq(int n){
    vector<int>ans;
    for(int i=2 ; i*i<=n; ++i){
        while(n%i==0){
            ans.pb(i);
            n/=i;
        }
    }
    if(n>1) ans.pb(n);
    return ans;
}

//---------------------------------------------------------------------

// const int NN=1e7+10;
// ll fact[NN];

// void initfact(){
//     fact[0]=1;
//     for (int i = 1; i < NN; ++i){
//         fact[i]=(i*fact[i-1]*1LL)%M;
//     }
// }

// ll nck(ll n,ll k){
//     ll ans=fact[n];
//     ll deno=(fact[k]*fact[n-k]*1LL)%M;
//     ans=(ans*binexp(deno,M-2,M)*1LL)%M;
//     return ans;
// }

//-------------------

// const int NN=1e7+10;
// vector<int>b(NN,1);
// // vector<int>hp(NN,0);

// void sieve(){
//     b[0]=b[1]=0;
//     for(int i=2; i<NN; i++){
//         if(b[i]){
//             // hp[i]=i;
//             for(int j=2*i; j<NN; j+=i){
//                 b[j]=0;
//                // hp[j]=i;
//             }
//         }
//     }
// }

// vector<int> pfsieve(int n){
//     vector<int>ans;
//     while(n>1){
//         int p=hp[n];
//         while(n%p==0){
//             n=n/p;
//             ans.pb(p);
//         }
//     }
//     return ans;
// }

//---------------------------------------------------------------------



void solve(){
    ll tt=1; 
    cin>>tt; 
    while(tt--){
        string s; cin>>s;
        ll n=sz(s);
        ll x; cin>>x;
        string tmp(n,'1');
        for(int i=0; i<n; i++){
            if(s[i]=='0'){
                if(i-x>=0) tmp[i-x]='0';
                if(i+x<n) tmp[i+x]='0';
            }
        }
        string a(n,'1');
        for(int i=0; i<n; i++){
            if(((i-x<0) || (i-x>=0 && tmp[i-x]=='0')) && ((i+x>=n) || (i+x<n && tmp[i+x]=='0'))) a[i]='0';
        }
        // cout<<tmp<<endl;
        // cout<<a<<endl;
        if(a==s) cout<<tmp<<endl;
        else cout<<-1<<endl;
    }
}


//---------------------------------------------------------------------
int main() {
    #ifndef ONLINE_JUDGE
      freopen("dbg.txt","w",stderr);
    #endif
    fastio();

    solve();
}